package com.adee.java;

import java.util.TreeMap;

/**
 * TreeMap使用及原理：https://www.cnblogs.com/shoshana-kong/p/17548762.html
 *
 * key不能为null，否则抛空指针异常。
 *
 * TreeMap 是 Java 集合框架中的一个类，它实现了 SortedMap 接口，可以存储键值对，
 * 并按照键的自然顺序或者指定的比较器进行排序。TreeMap 的底层是一棵红黑树，这是一种
 * 自平衡的二叉搜索树，可以保证在插入，删除，查找等操作中的时间复杂度为 O(log n)。
 *
 * 适用场景
 * TreeMap 是一种有序的映射，它可以在保证高效性的同时，提供一些基于排序的操作。因此，TreeMap 适用于以下场景：
 * 需要按照键的自然顺序或者指定的比较器进行排序的场景，例如字典，排行榜，日程安排等。
 * 需要快速找到映射中最小或者最大的键或者值的场景，例如优先队列，堆，区间查询等。
 * 需要快速找到映射中某个范围内的所有键或者值的场景，例如范围搜索，前缀匹配，区间统计等。
 *
 * 底层原理
 * TreeMap 的底层是一棵红黑树，这是一种自平衡的二叉搜索树，它满足以下性质：
 * 每个节点要么是红色，要么是黑色。
 * 根节点是黑色。
 * 每个叶子节点（空节点）是黑色。
 * 如果一个节点是红色，那么它的两个子节点都是黑色。
 * 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
 * 这些性质保证了红黑树在插入，删除，查找等操作中都能保持平衡。
 *
 * 构造方法
 * TreeMap 的构造方法有以下几个：
 * TreeMap()：创建一个空的 TreeMap，按照键的自然顺序进行排序。
 * TreeMap(Comparator<? super K> comparator)：创建一个空的 TreeMap，并指定一个比较器来对键进行排序。
 * TreeMap(Map<? extends K,? extends V> m)：创建一个 TreeMap，并将给定映射中的所有键值对添加到 TreeMap 中，并按照键的自然顺序进行排序。
 * TreeMap(SortedMap<K,? extends V> m)：创建一个 TreeMap，并将给定有序映射中的所有键值对添加到 TreeMap 中，并按照给定有序映射中的比较器或者自然顺序进行排序。
 *
 * 注意事项
 * 使用 TreeMap 时，需要注意以下几点：
 * 如果使用自然顺序进行排序，则需要保证键是可比较的（实现了 Comparable 接口），否则会抛出 ClassCastException 异常。
 * 如果使用指定的比较器进行排序，则需要保证比较器是一致的（满足自反性，对称性，传递性），否则可能导致排序结果不正确或者抛出 ClassCastException 异常。
 * 如果在遍历 TreeMap 的过程中修改了其结构（添加或删除了元素），则可能导致 ConcurrentModificationException 异常或者不确定的行为。
 * 如果在遍历 TreeMap 的过程中修改了其元素（改变了键或者值），则可能导致排序结果不正确或者不确定的行为。
 * TreeMap 不是线程安全的，如果多个线程同时访问或修改 TreeMap，则需要进行同步处理。
 *
 * 总结
 * TreeMap 是一种有序的映射，它可以存储键值对，并按照键的自然顺序或者指定的比较器进行排序。
 * TreeMap 的底层是一棵红黑树，这是一种自平衡的二叉搜索树，可以保证在插入，删除，查找等操作中
 * 的时间复杂度为 O(log n)。TreeMap 还提供了一些特有的方法，用于利用其排序特性进行操作。
 * 使用 TreeMap 时，需要注意一些细节，以避免出现异常或者不确定的行为。TreeMap 是 Java 集合
 * 框架中的一个重要的类，它在很多场景中都有着广泛的应用。
 *
 */
public class Test054_TreeMap {

    public static void main(String[] args) {
//        test1();
        test2();
    }

    public static void test1() {
        // 创建一个 TreeMap
        TreeMap<String, Integer> map = new TreeMap<>();

        // 向 TreeMap 中添加键值对
        map.put("Bob", 80);
        map.put("Charlie", 70);
        map.put("Alice", 90);
        map.put("David", 60);

        // 打印 TreeMap 的内容
        System.out.println(map); // {Alice=90, Bob=80, Charlie=70, David=60}

        // 根据键获取对应的值
        System.out.println(map.get("Alice")); // 90
        System.out.println(map.get("Eve")); // null

        // 根据键删除对应的键值对
        map.remove("Bob");
        System.out.println(map); // {Alice=90, Charlie=70, David=60}

        // 获取 TreeMap 中的键值对的数量
        System.out.println(map.size()); // 3

        // 判断 TreeMap 中是否包含某个键
        System.out.println(map.containsKey("Charlie")); // true
        System.out.println(map.containsKey("Eve")); // false

        // 判断 TreeMap 中是否包含某个值
        System.out.println(map.containsValue(70)); // true
        System.out.println(map.containsValue(50)); // false

        // 清空 TreeMap 中的所有键值对
        map.clear();
        System.out.println(map); // {}
    }

    public static void test2() {
        /**
         * 除了上述方法外，TreeMap 还提供了一些特有的方法，用于利用其排序特性进行操作。例如：
         *
         * firstKey 和 lastKey：分别返回 TreeMap 中最小和最大的键。
         * lowerKey 和 higherKey：分别返回 TreeMap 中小于和大于给定键的最近的键。
         * floorKey 和 ceilingKey：分别返回 TreeMap 中小于等于和大于等于给定键的最近的键。
         * subMap：返回一个子映射，包含给定范围内的所有键值对。
         * headMap 和 tailMap：分别返回一个子映射，包含小于或等于给定键或大于或等于给定键的所有键值对。
         * firstEntry 和 lastEntry：分别返回 TreeMap 中最小和最大的键值对。
         * lowerEntry 和 higherEntry：分别返回 TreeMap 中小于和大于给定键的最近的键值对。
         * floorEntry 和 ceilingEntry：分别返回 TreeMap 中小于等于和大于等于给定键的最近的键值对。
         * pollFirstEntry 和 pollLastEntry：分别返回并删除 TreeMap 中最小和最大的键值对。
         */
        // 创建一个 TreeMap
        TreeMap<String, Integer> map = new TreeMap<>();

        // 向 TreeMap 中添加键值对
        map.put("Alice", 90);
        map.put("Bob", 80);
        map.put("Charlie", 70);
        map.put("David", 60);

        // 打印 TreeMap 的内容
        System.out.println(map); // {Alice=90, Bob=80, Charlie=70, David=60}

        // 返回 TreeMap 中最小和最大的键
        System.out.println(map.firstKey()); // Alice
        System.out.println(map.lastKey()); // David

        // 返回 TreeMap 中小于和大于给定键的最近的键
        System.out.println(map.lowerKey("Bob")); // Alice
        System.out.println(map.higherKey("Bob")); // Charlie

        // 返回 TreeMap 中小于等于和大于等于给定键的最近的键
        System.out.println(map.floorKey("Bob")); // Bob
        System.out.println(map.ceilingKey("Bob")); // Bob

        // 返回一个子映射，包含给定范围内的所有键值对
        System.out.println(map.subMap("Alice", true, "Charl", true)); // {Alice=90, Bob=80, Charlie=70}

        // 返回一个子映射，包含小于或等于给定键或大于或等于给定键的所有键值对
        System.out.println(map.headMap("Charlie", true)); // {Alice=90, Bob=80, Charlie=70}
        System.out.println(map.tailMap("Charlie", true)); // {Charlie=70, David=60}

        // 返回 TreeMap 中最小和最大的键值对
        System.out.println(map.firstEntry()); // Alice=90
        System.out.println(map.lastEntry()); // David=60

        // 返回 TreeMap 中小于和大于给定键的最近的键值对
        System.out.println(map.lowerEntry("Bob")); // Alice=90
        System.out.println(map.higherEntry("Bob")); // Charlie=70

        // 返回 TreeMap 中小于等于和大于等于给定键的最近的键值对
        System.out.println(map.floorEntry("Bob")); // Bob=80
        System.out.println(map.ceilingEntry("Bob")); // Bob=80

        // 返回并删除 TreeMap 中最小和最大的键值对
        System.out.println(map.pollFirstEntry()); // Alice=90
        System.out.println(map.pollLastEntry()); // David=60
    }
}
